package com.fosss.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {

//        int[] arr={9,7,2,6,8,3};
//        System.out.println("排序前："+Arrays.toString(arr));
//        bubbleSort(arr);
//        System.out.println("排序后："+Arrays.toString(arr));

        //测试时间复杂度
        //创建一个80000条数据的数组
        int[] arr=new int[80000];
        for(int i = 0; i <80000;i++){
            arr[i]=(int)(Math.random()*80000);
        }
        long startTime = System.currentTimeMillis();
        bubbleSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("花费时间"+(endTime-startTime)+"毫秒");//8332

    }

    public static void bubbleSort(int[] arr){
        boolean flag=false;
        for (int i = 0; i < arr.length-1; i++) {//一共需要比较size-1次
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    flag=true;
                    int t=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=t;
                }
            }

//            System.out.printf("第%d次排序后的数组-> ",i+1);
//            System.out.println(Arrays.toString(arr));
            if(!flag){//优化：：判断flag是否为false,如果为false说明没有发生交换，排序已经完成，直接退出循环
                break;
            }else {
                flag=false;//！！！！！！！！！将flag重置
            }
        }
    }
}
